package com.lw.leetcode.arr.b;

import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * 498. 对角线遍历
 *
 * @author liw
 * @version 1.0
 * @date 2021/10/8 15:38
 */
public class FindDiagonalOrder {


    public static void main(String[] args) {
        FindDiagonalOrder test = new FindDiagonalOrder();

        // [1,2,4,7,5,3,6,8,9]
//        int[][] arr = {{1,2,3}, {4,5,6}, {7,8,9}, {17,18,19}, {27,28,29}};
        // [1,2,4,7,5,3,6,8,9]
        int[][] arr = {{1}, {2}, {3}, {4}, {5}};

        int[] diagonalOrder = test.findDiagonalOrder(arr);
        System.out.println(Arrays.toString(diagonalOrder));
    }


    public int[] findDiagonalOrder(int[][] mat) {
        int m = mat.length;
        int n = mat[0].length;
        int length = m * n;
        int[] arr = new int[length];
        int x1 = 0;
        int y1 = 0;
        int x2 = 0;
        int y2 = 1;
        if (n == 1) {
            x2 = 1;
            y2 = 0;
        }
        boolean flag = true;
        int index = 0;
        while (index < length) {
            if (flag) {
                int x = x1;
                int y = y1;
                while (index < length && x >= 0 && y < n) {
                    arr[index++] = mat[x][y];
                    x--;
                    y++;
                }
                if (x1 + 2 - m < 0) {
                    x1 += 2;
                } else if (x1 + 2 - m == 0){
                    x1++;
                    y1++;
                } else {
                    y1 += 2;
                }
            } else {
                int x = x2;
                int y = y2;
                while (index < length && x < m && y >= 0) {
                    arr[index++] = mat[x][y];
                    x++;
                    y--;
                }
                if (y2 + 2 - n < 0) {
                    y2 += 2;
                } else if (y2 + 2 - n == 0){
                    x2++;
                    y2++;
                } else {
                    x2 += 2;
                }
            }
            flag = !flag;
        }
       return arr;
    }
}
